/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
    let res = [],
        pointQ = [],
        row = new Array(n).fill(".");
    solveNQueenLevel(n, res, [], 0);
    for (let i = 0; i < res.length; i++) {
        let temp = []
        for (let j = 0; j < n; j++) {
            row[res[i][j]] = "Q"
            temp.push(row.join(""))
            row[res[i][j]] = "."
        }
        pointQ.push(temp)
    }
    return pointQ
};

function solveNQueenLevel(n, res, valArr) {
    if (valArr.length === n) {
        res.push(valArr.slice())
        return
    }

    for (let i = 0; i < n; i++) {
        let canUse = true
        // 从第二行开始判断位置是否可以使用，如果在第n行，前n-1行的j值i都不可以使用，第一行的第二个位置的和左下角的和相同，和右下角的差相同（列值-行值）
        if (valArr.length >= 1) {
            for (let j = 0; j < valArr.length; j++) {
                if (valArr[j] - j === i - valArr.length) {
                    canUse = false
                    break
                }
                if (valArr[j] + j === i + valArr.length) {
                    canUse = false
                    break
                }
                if (valArr[j] === i) {
                    canUse = false
                    break
                }
            }
        }
        if (!canUse) {
            continue
        }
        valArr.push(i)
        solveNQueenLevel(n, res, valArr)
        valArr.pop()
    }
}